﻿#ifndef __SS_SORT_H__
#define __SS_SORT_H__
#include "../tools/ssRandom.h"
#include "../tools/ssSwap.h"

namespace StarSeeker
{
	//冒泡排序
	template <class T>
	inline void BubbleSort(T *t, u32 count, bool ascending=true)
	{
		for (u32 i = 0; i < count; ++i)
		{
			for (u32 j = i + 1; j < count; ++j)
			{
				if (ascending)
				{
					if (t[i] < t[j])
						Swap(t[j], t[i]);
				} 
				else
				{
					if (t[i] > t[j])
						Swap(t[j], t[i]);
				}
			}
		}
	}

	//选择排序
	template <class T>
	inline void SelectSort(T *t, u32 count, bool ascending)
	{
		T tmp = 0;
		T min = 0;
		for (u32 i = 0; i < count; i++)
		{
			min = i;
			for (u32 j = i + 1; j < count; j++)
			{
				if (ascending)
				{
					if (t[min] > t[j])
					{
						min = j;
					}
				}
				else
				{
					if (t[min] < t[j])
					{
						min = j;
					}
				}
			}
			Swap(t[min], t[i]);
		}
	}

	//希尔排序
	template <class T>
	inline void ShellSort(T *t, u32 count, bool ascending = true)
	{
		for (u32 h = count / 2; h > 0; h = h / 2)
		{
			for (u32 i = h; i < count; i++)
			{
				int temp = t[i];
				if (ascending)
				{
					if (temp < t[i - h])
					{
						for (int j = 0; j < i; j += h)
						{
							if (temp < t[j])
							{
								temp = t[j];
								t[j] = t[i];
								t[i] = temp;
							}
						}
					}
				}
				else
				{
					if (temp > t[i - h])
					{
						for (int j = 0; j < i; j += h)
						{
							if (temp > t[j])
							{
								temp = t[j];
								t[j] = t[i];
								t[i] = temp;
							}
						}
					}
				}
			}
		}
	}

	//快速排序
	template <class T>
	inline void QuickSort(T *t, u32 beg, u32 end)
	{
		if (beg + 1 < end)
		{
			T middle = t[(beg + end) / 2];
			u32 i = beg - 1;
			u32 j = end + 1;
			while (true)
			{
				while (t[++i] < middle && i < end);
				while (t[--j] > middle && j > 0);
				if (i >= j)
					break;

				Swap(t[j], t[i]);
			}
			QuickSort(t, beg, i - 1);
			QuickSort(t, j + 1, end);
		}
	}

	//打乱数组(洗牌算法)
	template<class T>
	inline void ShuffleArray(T* t, u32 count)
	{
		u32 num = count - 1;
		u32 offset = 0;
		for (u32 i = 0; i < num; ++i)
		{
			offset = SS_RAND->RandU32(i, num);
			Swap(t[offset], t[i]);
		}
	}
}

#endif
